/**************************************************************************************
*
*	Copyright (C) 2009 Brent Andrew Chua - See LICENSE.txt for more info.
*		
*	Filename	-	Hashtable.h
*
*	Description -	Hashtable or unsorted map?
*
*	Comments	- Uses quadratic probing.
*					
*	Modification History:
*			Name			   Date					Description
*			CodeSushi	-	11/15/2009	-	Creation of this file
**************************************************************************************/

#ifndef _PSX_HASH_TABLE_H_
#define _PSX_HASH_TABLE_H_

#include "PTLBase.h"
#include "Array.h"

namespace Pulse
{
	template < typename T >
	class HashTable
	{
	public:

		HashTable( void );

		void Clear( void );
		PSX_CRef< T > Find( const T &obj ) const;
		void Insert( const T &obj );
		void Remove( const T &obj );

	private:
		
		enum EntryType { ACTIVE, EMPTY, DELETED };
		struct HashEntry
		{
			T m_elem;
			EntryType m_entryInfo;

			HashEntry( const T &elem = T(), EntryType eType = EMPTY );
		};
	
		BOOL IsActive( UINT currentPos ) const;
		UINT FindPos( const T &obj ) const;
		void Rehash( void );

		Array< HashEntry > m_array;
		SIZE_T m_numOccupied;

	};

	/* HashEntry Implementation */
	template < typename T >
	HashTable< T >::HashEntry::HashEntry( const T &elem /*= T()*/, EntryType eType /*= EMPTY*/ )
		: m_elem( elem ), m_entryInfo( eType )
	{
	}

	/* HashTable Implementation */

	template < typename T >
	HashTable< T >::HashTable( void ) : m_array( PSX_NextPrime( 101 ) )
	{
		Clear();
	}

	// Make the hash table logically empty
	template < typename T >
	void HashTable< T >::Clear( void )
	{
		m_numOccupied = 0;
		for ( SIZE_T i = 0; i < m_array.GetSize(); ++i )
			m_array[i].m_entryInfo = EMPTY;
	}

	// Find item x in the hash table.
	// Returned item wrapped in CRef object
	template < typename T >
	PSX_CRef< T > HashTable< T >::Find( const T &obj ) const
	{
		UINT currPos = FindPos( obj );

		if ( IsActive( currPos ) )
			return PSX_CRef< T >( m_array[ currPos ].m_elem );
		else
			return PSX_CRef< T >();
	}

	template < typename T >
	BOOL  HashTable< T >::IsActive( UINT currPos ) const
	{
		return m_array[ currPos ].m_entryInfo == ACTIVE;
	}

	template < typename T >
	void HashTable< T >::Remove( const T &obj )
	{
		UINT currPos = FindPos( obj );
		if ( IsActive( currPos ) )
			m_array[ currPos ].m_entryInfo = DELETED;
		else
			PSX_ThrowAssert( false, "Item not found" );
	}

	template < typename T >
	void HashTable< T >::Insert( const T &obj )
	{
		UINT currPos = FindPos( obj );
		
		if ( IsActive( currPos ) )
			PSX_ThrowAssert( false, "Duplicate item exception." );

		m_array[ currPos ] = HashEntry( obj, ACTIVE );

		if ( ++m_numOccupied > m_array.GetSize() / 2 )
			Rehash();
	}

	// Expand the hash table
	template < typename T >
	void HashTable< T >::Rehash( void )
	{
		SIZE_T i;
		Array< HashEntry > oldArray = m_array;

		// Create a double size empty table
		m_array.Resize( PSX_NextPrime( 2 * oldArray.GetSize() ) );
		for ( i = 0; i < m_array.GetSize(); ++i )
			m_array[i].m_entryInfo = EMPTY;

		// Copy table over
		Clear();
		for ( i = 0; i < oldArray.GetSize(); ++i )
			if ( oldArray[i].m_entryInfo == ACTIVE )
				Insert( oldArray[i].m_elem );
	}

	template < typename T >
	UINT HashTable< T >::FindPos( const T &obj ) const
	{
		UINT i = 0;
		UINT currPos = PSX_SuperFastHash( obj ) % m_array.GetSize();

		while ( m_array[currPos].m_entryInfo != EMPTY && m_array[currPos].m_elem != obj )
		{
			currPos += 2 * ++i - 1; // compute ith probe
			if ( currPos >= m_array.GetSize() )
				currPos -= m_array.GetSize();
		}
		return currPos;
	}
}

#endif /* _PSX_HASH_TABLE_H_ */